Матч 237, Деление торта (CakeDivision)

Дивизион 1, Уровень 2

Торт прямоугольной формы, имеющего длину length и ширину width, следует разрезать на pieces частей прямоугольной формы. Каждое разрезание проходит параллельно сторонам куска и разделяет его на две прямоугольные части. Таким образом, для разрезания торта на n кусков следует совершить n – 1 разрезаний.

Отношением куска будем называть частное от деления его длины на ширину. Разрезание следует провести так, чтобы максимум отношения кусков был наименьшим.

Например, пусть следует разрезать торт 5*5 на 5 кусков. Первым разрезом делим торт на два куска размерами 2*5 и 3*5. Меньший кусок (2*5) делим на два равных куска, а больший (3*5) – на три. Получаем 5 кусков двух типов: 2*5/2 и 3*5/3. Отношение куска первого типа равно 2 / 5/2 = 4/5 = 0.8, второго 3 / 5/3 = 9/5 = 1.8. Их максимум равен 1.8, который меньше сделать никак нельзя.

Класс: CakeDivision

Метод: double ratio(int length, int width, int pieces)

Ограничения: 1 £ length, width £ 1000, 1 £ pieces £ 10.

Вход. Длина length и ширина width торта, количество кусков pieces, на которое его следует разрезать.

Выход. Наименьшее возможное значение максимума отношения кусков.

Пример входа

length	width	pieces
2	3	6
5	5	5
950	430	9

Пример выхода

1.0

1.8

1.2573099415204678

РЕШЕНИЕ

рекурсия + полный перебор

Благодаря верхнему ограничению на число кусков pieces, задача может быть просто решена полным перебором разрезаний торта. Если кусок размером length на width следует разбить на pieces кусков, то первый разрез можно сделать либо по горизонтали, либо по вертикали. При этом площади двух полученных кусков должны быть пропорциональны числам 1 и pieces – 1, или 2 и pieces – 2 и так далее. То есть после первого разреза должны получаться два куска размером i * length / pieces на width и ((pieces – i ) * length / pieces на width, или length на i * width / pieces и length на (pieces – i) * width / pieces, где 1 £ i < pieces. При этом дальше первый кусок следует делить на i кусков, а второй на pieces – i кусков.

Если исходный кусок разбивается на две горизонтальные (вертикальные) полосы, то их ширина (длина) должна быть одинаковой.

Совершаем разрез исходного куска на две части и далее рекурсивно запускаем разрезание каждой из полученных частей. Ищем такое разрезание, при котором максимум отношения кусков является наименьшим.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

using namespace std;

double cut(double length, double width, int pieces)

{

double temp, res = 1e100;

int i;

if (pieces == 1) return max(length,width) / min(length,width);

for(i = 1; i < pieces; i++)

{

temp = max(cut(i * length / pieces,width,i),cut((pieces - i) *

length / pieces,width,pieces - i));

if (temp < res) res = temp;

}

for(i = 1; i < pieces; i++)

{

temp = max(cut(length,i * width / pieces,i),cut(length,(pieces - i) *

width / pieces,pieces - i));

if (temp < res) res = temp;

}

return res;

}

class CakeDivision

{

public:

double ratio(int length, int width, int pieces)

{

return cut(length,width,pieces);

}

};